pacman::p_load(data.table,forecast, tseries, fUnitRoots, tidyverse, fastDummies, lmtest, readxl, ggpubr, reshape2)
#set wd to this R file's current folder.
#setwd(dirname(rstudioapi::getActiveDocumentContext()$path))

Datasets

amtrak = read.csv("AmtrakBig_CA_Question-3.csv")
head(amtrak)
#convert to ts
amtrakts = ts(amtrak$Ridership, start = c(2005,1), frequency = 12)
amtrakts
      Jan  Feb  Mar  Apr  May  Jun  Jul  Aug  Sep  Oct  Nov  Dec
2005 1709 1621 1973 1812 1975 1862 1940 2013 1596 1725 1676 1814
2006 1615 1557 1891 1956 1885 1623 1903 1997 1704 1810 1862 1875
2007 1705 1619 1837 1957 1917 1882 1933 1996 1673 1753 1720 1734
2008 1563 1574 1903 1834 1831 1776 1868 1907 1686 1779 1776 1783
2009 1548 1497 1798 1733 1772 1761 1792 1875 1571 1647 1673 1657
2010 1382 1361 1559 1608 1697 1693 1836 1943 1551 1687 1576 1700
2011 1397 1372 1708 1655 1763 1776 1934 2008 1616 1774 1732 1797
2012 1570 1413 1755 1825 1843 1826 1968 1922 1670 1791 1817 1847
2013 1599 1549 1832 1840 1846 1865 1966 1949 1607 1804 1850 1836
2014 1542 1617 1920 1971 1992 2010 2054 2097 1824 1977 1981 2000
2015 1683 1663 2008 2024 2047 2073 2127 2203 1708 1951 1974 1985
2016 1760 1771 2020 2048 2069 1994 2075 2027 1734 1917 1858 1996
2017 1778 1749 2066 2099 2105 2130 2223 2174 1931 2121 2076 2141
2018 1832 1838 2132                                             

TS Plot

autoplot(amtrakts) + labs(y="Ridership") +
  annotate("rect", xmin = 2008, xmax = 2011, ymin = 1200, ymax = 2500,
           alpha = .2, fill = "yellow") +
  annotate("rect", xmin = 2010, xmax = 2016, ymin = 1200, ymax = 2500,
           alpha = .1, fill = "blue") + 
  annotate("rect", xmin = 2016, xmax = 2018.25, ymin = 1200, ymax = 2500,
           alpha = .2, fill = "blue") + 
  scale_x_continuous(breaks = seq(2005, 2019, by = 1)) +
  annotate("segment", x = 2010, y = 2500, xend = 2018.25, yend = 2500, arrow = arrow(ends = "both", type = "open")) +
  annotate("segment", x = 2008, y = 1800, xend = 2011, yend = 1500, color = "red", arrow = arrow(length = unit(0.25, "cm"), type = "closed")) +
  annotate("text", x = c(2009.5,2013,2017.15, 2014), y = c(2400,2400,2400,2550), label = c("Declining Trend","Training Data","Test Data","Modelling Data"), size = 8)

Decomposition Plot

plot(decompose(amtrakts))

there is yearly seasonality. and uptrend starts at 2010.

uptrend = window(amtrakts, start = c(2010,1))
frequency(amtrakts)
[1] 12

Lag Plot

gglagplot(amtrakts)

Seasonal Plot

ggseasonplot(uptrend) + labs(y="Ridership") 

Differencing

#plot tsdisplay
ggtsdisplay(uptrend, smooth = TRUE)

#non-stationarity, try 1st order differencing.
uptrend %>%
  diff() %>%
  ggtsdisplay(smooth = TRUE)

#ACF Lag plots show seasonality at 12.
uptrend %>%
  diff() %>%
  diff(lag = 12) %>%
  ggtsdisplay(smooth = TRUE)

#try ndiffs and NSdiffs
ndiffs(uptrend)
[1] 1
nsdiffs(uptrend)
[1] 1

Partition for Train and Test Set

training = window(uptrend, end = c(2015,12))
test = window(uptrend, start = c(2016,1))

Setting Up Functions

Compute errors and return as a vector for comparison

errorcalc = function(fit,test){
  #test is the ts you want to test against
  if (missing(test)) {
    #compute accuracy and return vector
    acc = accuracy(fit)
    return(acc[1,])
  } else {
    fc = forecast(fit,length(test))
    acc = accuracy(fc,test)
    return(acc[2,])
  }
}

Run all arima models for selection

# runarima 
runarima = function(training, a, d){
  if (!missing(d)) {
    fit = Arima(training, c(a[1],d,a[2]), seasonal = c(a[3],d,a[4]))
    return(fit)
  } else {
    fit = Arima(training, c(a[1],a[2],a[3]), seasonal = c(a[4],a[5],a[6]))
    return(fit)
  }
}

ARIMA Modelling

# Create an arima model for each of them, given that d,D = 1.
#run total of 81 sets of parameters for p,q,P,Q %in% 0:2
arima_para = expand.grid(rep(list(0:2), 4))
arimalist = list()
for (i in 1:nrow(arima_para)) {
  tryCatch( {
    arimalist[[i]] <- runarima(training,as.numeric(arima_para[i,]),1)
  },
  error = function(cond) {
    return(NA)
  }
  )
}
#Check null models. These are models that might be unstable and couldn't be built (no suitable parameters found)
nullvals = !sapply(arimalist, is.null)
fitlist_nonull = arimalist[nullvals]
para_nonull = arima_para[nullvals,]
aicc = list()
for (i in 1:length(fitlist_nonull)) {
  aicc[[i]] <- fitlist_nonull[[i]][["aicc"]]
}
#visualize AICC
aicc = as.numeric(aicc)
fcerrors = as.data.frame(t(sapply(fitlist_nonull,'errorcalc',test)))
#checkparameters of optimized model, selected based on comparison with test set or AICC.
#RMSE, MAE, AICC
para_nonull[which.min(fcerrors$RMSE),]
para_nonull[which.min(fcerrors$MAE),]
para_nonull[which.min(aicc),]
plotarima = list(fitlist_nonull[[which.min(fcerrors$RMSE)]],fitlist_nonull[[which.min(fcerrors$MAE)]],fitlist_nonull[[which.min(aicc)]])
plotarimaerror = as.data.frame(t(sapply(plotarima,'errorcalc',test)))
fitrows = c('Min RMSE','Min MAE','Min AICc')
plotarimaerror$Fits <- as.factor(fitrows)
plotarimaerror %>%
  melt(id.vars = "Fits") %>%
  ggplot(aes(x = variable, y = value)) + 
  geom_bar(aes(fill = Fits), stat = 'identity', position = 'dodge') + 
  labs(title = "Errors on test set") + facet_wrap(~variable, scale = "free")

Compare to test set

autoplot(window(amtrakts, start = c(2014,1))) + labs(y="Ridership") +
  autolayer(forecast(plotarima[[1]],length(test)), series = 'Min RMSE', PI = FALSE) +
  autolayer(forecast(plotarima[[2]],length(test)), series = 'Min MAE', PI = FALSE) +
  autolayer(forecast(plotarima[[3]],length(test)), series = 'Min AICc', PI = FALSE) +
  annotate("rect", xmin = 2016, xmax = 2018.5, ymin = 1500, ymax = 2300,
           alpha = .1, fill = "yellow") +
  annotate("text", x = 2016.5, y = 2250, label = c("Test Period"), size = 10)

#Selection of Min MAE (111,011) and Min RMSE (212,212) as model.
selectedmodels = list(fitlist_nonull[[which.min(fcerrors$RMSE)]],fitlist_nonull[[which.min(fcerrors$MAE)]])

Try out ets model

# Recalling previous decomposition plots, we should expect additive seasonality and trend components.
#i.e our ets model should yield ets(-,A,A)
fitets = ets(training)
fitets = ets(training, model = "ZAA")
#model chose AAA ets model. 
#try ZMM, ZAM, ZMA models, AIC did not improve.
ets(training, model = "ZMM")
ETS(M,Md,M) 

Call:
 ets(y = training, model = "ZMM") 

  Smoothing parameters:
    alpha = 0.4286 
    beta  = 2e-04 
    gamma = 6e-04 
    phi   = 0.98 

  Initial states:
    l = 1576.1972 
    b = 1.0047 
    s = 1.0209 0.9999 1.0081 0.9237 1.1228 1.0986
           1.0419 1.0403 1.0206 1.0127 0.8438 0.8666

  sigma:  0.029

     AIC     AICc      BIC 
892.8189 905.7246 933.7989 
# ets(training, model = "ZMA")
# Error in ets(training, model = "ZMA") : No model able to be fitted
selectedmodels[[length(selectedmodels)+1]] <- fitets
#Compare accuracy against test set.
accuracy(predict(fitets, length(test)), test)
                     ME     RMSE      MAE        MPE     MAPE      MASE       ACF1
Training set  -1.103143 45.47889 34.35939 -0.1110417 1.955833 0.4463224 0.08944136
Test set     -26.430079 71.22510 47.91802 -1.3316154 2.470417 0.6224467 0.70601168
             Theil's U
Training set        NA
Test set     0.4385423
# Plot forecast from ETS(A,A,A)
autoplot(window(amtrakts, start = c(2010,1))) + labs(y="Ridership") +
  autolayer(forecast(fitets,length(test)), PI = TRUE) +  
  labs(title = "Forecast from ETS(A,A,A)")

Try tsCv

#use tsCV to check our models. Start with ets.
myforecast = function(y,h) {
  forecast(ets(y, model = "ZAA"),h = h)
}
RMSEcalc = function(a) {
  sqrt(mean(a^2, na.rm = TRUE))
}
MAEcalc = function(a) {
  mean(abs(a), na.rm = TRUE)
}
NAcalc = function(a) {
  sum(is.na(a))
}
tsCVets = tsCV(uptrend, myforecast, h = 12)
# compute RMSE/MAE/NA for forecast window. We also remove the first 14 figures as arima cannot build a model without 1 year of seasonality.
tsCVets = window(tsCVets, start = c(2011,3))
RMSEets = apply(tsCVets, 2, RMSEcalc)
MAEets = apply(tsCVets, 2, MAEcalc)
NAets = apply(tsCVets, 2, NAcalc)
#tsCV on arima(212,212)
myforecast = function(y,h){
  forecast(arima(y, order = c(2,1,2), seasonal = c(2,1,2)),h = h)
}
tsCVarima212212 = tsCV(uptrend, myforecast, h = 12)
tsCVarima212212 = window(tsCVarima212212, start = c(2011,3))
RMSEarima2 = apply(tsCVarima212212, 2, RMSEcalc)
MAEarima2 = apply(tsCVarima212212, 2, MAEcalc)
NAarima2 = apply(tsCVarima212212, 2, NAcalc)
myforecast = function(y,h){
  forecast(arima(y, order = c(1,1,1), seasonal = c(0,1,1)),h = h)
}
tsCVarima111011 = tsCV(uptrend, myforecast, h = 12)
tsCVarima111011 = window(tsCVarima111011, start = c(2011,3))
RMSEarima1 = apply(tsCVarima111011, 2, RMSEcalc)
MAEarima1 = apply(tsCVarima111011, 2, MAEcalc)
NAarima1 = apply(tsCVarima111011, 2, NAcalc)
RMSE = as.data.frame(cbind(RMSEets,RMSEarima2,RMSEarima1))
colnames(RMSE) = c("etsAAA","arima212212","arima111011")
RMSE = RMSE %>%
  rownames_to_column("h") %>%
  mutate(error = "RMSE")
MAE = as.data.frame(cbind(MAEets,MAEarima2,MAEarima1))
colnames(MAE) = c("etsAAA","arima212212","arima111011")
MAE = MAE %>%
  rownames_to_column("h") %>%
  mutate(error = "MAE")
NAs = as.data.frame(cbind(NAets,NAarima2,NAarima1))
colnames(NAs) = c("etsAAA","arima212212","arima111011")
NAs = NAs %>%
  rownames_to_column("h") %>%
  mutate(error = "NAs")
errors = rbind(RMSE,MAE,NAs) %>%
  melt(id.vars = c("h","error"), variable.name = "model")
errors$h %>%
  str_extract("\\d{1,2}") %>%
  as.integer() -> errors$h
errors %>%
  filter(error == "NAs") %>% filter(h == 1) %>%
  ggplot(aes(x = model)) +
  geom_col(aes(y=value, fill=model)) + facet_wrap(~error) +
  labs(title = "TS Cross Validation Results") + xlab("Model") + ylab("Number of Unstable Models") +
  scale_fill_manual(values = c("#22b8d6", "#4922d6","#228b75"))

errors %>%
  filter(error != "NAs") %>% filter(model != "arima212212") %>%
  ggplot(aes(x = h, y=value, color=model)) +
  geom_smooth(se = FALSE, size = 1.5) +
  geom_point(size = 2) + 
  facet_wrap(~error, nrow = 3) +
  labs(title = "TS Cross Validation Results") + 
  scale_x_continuous(breaks = seq(1, 12, by = 1)) +
  scale_color_manual(values = c("#22b8d6", "#228b75"))

Retrain complete model to forecast 6 months forward

fitarima_complete = arima(uptrend, order = c(1,1,1), seasonal = c(0,1,1))
fitets_complete = ets(uptrend, model = "ZAA")
autoplot(window(amtrakts, start = c(2016,1))) + labs(y="Ridership") +
  autolayer(forecast(fitarima_complete,12), series = 'Arima 111011', PI = FALSE, alpha = 0.5) +
  autolayer(forecast(fitets_complete,12), series = 'ETS "AAA"', PI = FALSE, alpha = 0.5) +
  scale_color_manual(values = c("red","green"))+
  annotate("rect", xmin = 2018.25, xmax = 2018.75, ymin = 1700, ymax = 2400,
           alpha = .2, fill = "blue") +
  annotate("rect", xmin = 2018.75, xmax = 2019.25, ymin = 1700, ymax = 2400,
           alpha = .1, fill = "yellow") +
  annotate("text", x = c(2018.5,2019), y = c(1800,1800), label = c("Apr-Sep '18","Oct-Mar '19"), size = 6) + 
  labs(title = "Amtrak ridership forecast")

p1 = autoplot(window(amtrakts, start = c(2014,1))) + labs(y="Ridership") +
  autolayer(forecast(fitarima_complete,12), series = 'Arima 111011', PI = TRUE, colour = "red") + 
  labs(title = "forecast with Arima111011")
p2 = autoplot(window(amtrakts, start = c(2014,1))) + labs(y="Ridership") +
  autolayer(forecast(fitarima_complete,12), series = 'ets_AAA', PI = TRUE, colour = "green") + 
  labs(title = "forecast with ets_AAA")
forecastarima = forecast(fitarima_complete, 12)
forecastets = forecast(fitets_complete,12)
ggarrange(p1,p2,nrow = 2, ncol = 1)

LS0tCnRpdGxlOiAiQ0ExIFNCIFBBIFF1ZXN0aW9uIDMiCmF1dGhvcjogQ2hpYSBIYXIgVGVjayBBbHZpbiwgCiAgICAgICAgS2hvbyBNYXkgU3plLCAKICAgICAgICBMaW0gWmhlbmd5aSBBbmR5LCAKICAgICAgICBMb3cgSmlhIFNoZW5nIE5lbHNvbiwgCiAgICAgICAgU3VtIEt3b2sgSG9vbmcgKEJyaWFuKQpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sKLS0tCgpgYGB7ciBzZXR1cCwgaW5jbHVkZT1GQUxTRX0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KGVjaG8gPSBUUlVFKQpgYGAKCmBgYHtyLCBtZXNzYWdlPUZBTFNFfQoKcGFjbWFuOjpwX2xvYWQoZGF0YS50YWJsZSxmb3JlY2FzdCwgdHNlcmllcywgZlVuaXRSb290cywgdGlkeXZlcnNlLCBmYXN0RHVtbWllcywgbG10ZXN0LCByZWFkeGwsIGdncHViciwgcmVzaGFwZTIpCgojc2V0IHdkIHRvIHRoaXMgUiBmaWxlJ3MgY3VycmVudCBmb2xkZXIuCiNzZXR3ZChkaXJuYW1lKHJzdHVkaW9hcGk6OmdldEFjdGl2ZURvY3VtZW50Q29udGV4dCgpJHBhdGgpKQoKYGBgCgojIERhdGFzZXRzCmBgYHtyfQphbXRyYWsgPSByZWFkLmNzdigiQW10cmFrQmlnX0NBX1F1ZXN0aW9uLTMuY3N2IikKCmhlYWQoYW10cmFrKQojY29udmVydCB0byB0cwoKYW10cmFrdHMgPSB0cyhhbXRyYWskUmlkZXJzaGlwLCBzdGFydCA9IGMoMjAwNSwxKSwgZnJlcXVlbmN5ID0gMTIpCmFtdHJha3RzCmBgYAoKIyBUUyBQbG90CmBgYHtyLCBtZXNzYWdlPUZBTFNFLCBmaWcuaGVpZ2h0PTQsIGZpZy53aWR0aD02fQphdXRvcGxvdChhbXRyYWt0cykgKyBsYWJzKHk9IlJpZGVyc2hpcCIpICsKICBhbm5vdGF0ZSgicmVjdCIsIHhtaW4gPSAyMDA4LCB4bWF4ID0gMjAxMSwgeW1pbiA9IDEyMDAsIHltYXggPSAyNTAwLAogICAgICAgICAgIGFscGhhID0gLjIsIGZpbGwgPSAieWVsbG93IikgKwogIGFubm90YXRlKCJyZWN0IiwgeG1pbiA9IDIwMTAsIHhtYXggPSAyMDE2LCB5bWluID0gMTIwMCwgeW1heCA9IDI1MDAsCiAgICAgICAgICAgYWxwaGEgPSAuMSwgZmlsbCA9ICJibHVlIikgKyAKICBhbm5vdGF0ZSgicmVjdCIsIHhtaW4gPSAyMDE2LCB4bWF4ID0gMjAxOC4yNSwgeW1pbiA9IDEyMDAsIHltYXggPSAyNTAwLAogICAgICAgICAgIGFscGhhID0gLjIsIGZpbGwgPSAiYmx1ZSIpICsgCiAgc2NhbGVfeF9jb250aW51b3VzKGJyZWFrcyA9IHNlcSgyMDA1LCAyMDE5LCBieSA9IDEpKSArCiAgYW5ub3RhdGUoInNlZ21lbnQiLCB4ID0gMjAxMCwgeSA9IDI1MDAsIHhlbmQgPSAyMDE4LjI1LCB5ZW5kID0gMjUwMCwgYXJyb3cgPSBhcnJvdyhlbmRzID0gImJvdGgiLCB0eXBlID0gIm9wZW4iKSkgKwogIGFubm90YXRlKCJzZWdtZW50IiwgeCA9IDIwMDgsIHkgPSAxODAwLCB4ZW5kID0gMjAxMSwgeWVuZCA9IDE1MDAsIGNvbG9yID0gInJlZCIsIGFycm93ID0gYXJyb3cobGVuZ3RoID0gdW5pdCgwLjI1LCAiY20iKSwgdHlwZSA9ICJjbG9zZWQiKSkgKwogIGFubm90YXRlKCJ0ZXh0IiwgeCA9IGMoMjAwOS41LDIwMTMsMjAxNy4xNSwgMjAxNCksIHkgPSBjKDI0MDAsMjQwMCwyNDAwLDI1NTApLCBsYWJlbCA9IGMoIkRlY2xpbmluZyBUcmVuZCIsIlRyYWluaW5nIERhdGEiLCJUZXN0IERhdGEiLCJNb2RlbGxpbmcgRGF0YSIpLCBzaXplID0gOCkKYGBgCgojIERlY29tcG9zaXRpb24gUGxvdApgYGB7cn0KcGxvdChkZWNvbXBvc2UoYW10cmFrdHMpKQpgYGAKCj4gdGhlcmUgaXMgeWVhcmx5IHNlYXNvbmFsaXR5LiBhbmQgdXB0cmVuZCBzdGFydHMgYXQgMjAxMC4KCmBgYHtyfQp1cHRyZW5kID0gd2luZG93KGFtdHJha3RzLCBzdGFydCA9IGMoMjAxMCwxKSkKZnJlcXVlbmN5KGFtdHJha3RzKQpgYGAKCiMgTGFnIFBsb3QKYGBge3J9CmdnbGFncGxvdChhbXRyYWt0cykKYGBgCgojIFNlYXNvbmFsIFBsb3QKYGBge3J9Cmdnc2Vhc29ucGxvdCh1cHRyZW5kKSArIGxhYnMoeT0iUmlkZXJzaGlwIikgCmBgYAoKIyBEaWZmZXJlbmNpbmcKYGBge3J9CiNwbG90IHRzZGlzcGxheQpnZ3RzZGlzcGxheSh1cHRyZW5kLCBzbW9vdGggPSBUUlVFKQoKI25vbi1zdGF0aW9uYXJpdHksIHRyeSAxc3Qgb3JkZXIgZGlmZmVyZW5jaW5nLgp1cHRyZW5kICU+JQogIGRpZmYoKSAlPiUKICBnZ3RzZGlzcGxheShzbW9vdGggPSBUUlVFKQoKI0FDRiBMYWcgcGxvdHMgc2hvdyBzZWFzb25hbGl0eSBhdCAxMi4KCnVwdHJlbmQgJT4lCiAgZGlmZigpICU+JQogIGRpZmYobGFnID0gMTIpICU+JQogIGdndHNkaXNwbGF5KHNtb290aCA9IFRSVUUpCgojdHJ5IG5kaWZmcyBhbmQgTlNkaWZmcwpuZGlmZnModXB0cmVuZCkKbnNkaWZmcyh1cHRyZW5kKQpgYGAKCiMgUGFydGl0aW9uIGZvciBUcmFpbiBhbmQgVGVzdCBTZXQKYGBge3J9CnRyYWluaW5nID0gd2luZG93KHVwdHJlbmQsIGVuZCA9IGMoMjAxNSwxMikpCnRlc3QgPSB3aW5kb3codXB0cmVuZCwgc3RhcnQgPSBjKDIwMTYsMSkpCmBgYAoKIyBTZXR0aW5nIFVwIEZ1bmN0aW9ucwojIyBDb21wdXRlIGVycm9ycyBhbmQgcmV0dXJuIGFzIGEgdmVjdG9yIGZvciBjb21wYXJpc29uCmBgYHtyfQplcnJvcmNhbGMgPSBmdW5jdGlvbihmaXQsdGVzdCl7CiAgI3Rlc3QgaXMgdGhlIHRzIHlvdSB3YW50IHRvIHRlc3QgYWdhaW5zdAogIGlmIChtaXNzaW5nKHRlc3QpKSB7CiAgICAjY29tcHV0ZSBhY2N1cmFjeSBhbmQgcmV0dXJuIHZlY3RvcgogICAgYWNjID0gYWNjdXJhY3koZml0KQogICAgcmV0dXJuKGFjY1sxLF0pCiAgfSBlbHNlIHsKICAgIGZjID0gZm9yZWNhc3QoZml0LGxlbmd0aCh0ZXN0KSkKICAgIGFjYyA9IGFjY3VyYWN5KGZjLHRlc3QpCiAgICByZXR1cm4oYWNjWzIsXSkKICB9Cn0KYGBgCgojIyBSdW4gYWxsIGFyaW1hIG1vZGVscyBmb3Igc2VsZWN0aW9uCmBgYHtyfQojIHJ1bmFyaW1hIApydW5hcmltYSA9IGZ1bmN0aW9uKHRyYWluaW5nLCBhLCBkKXsKICBpZiAoIW1pc3NpbmcoZCkpIHsKICAgIGZpdCA9IEFyaW1hKHRyYWluaW5nLCBjKGFbMV0sZCxhWzJdKSwgc2Vhc29uYWwgPSBjKGFbM10sZCxhWzRdKSkKICAgIHJldHVybihmaXQpCiAgfSBlbHNlIHsKICAgIGZpdCA9IEFyaW1hKHRyYWluaW5nLCBjKGFbMV0sYVsyXSxhWzNdKSwgc2Vhc29uYWwgPSBjKGFbNF0sYVs1XSxhWzZdKSkKICAgIHJldHVybihmaXQpCiAgfQp9CmBgYAoKIyBBUklNQSBNb2RlbGxpbmcKYGBge3J9CiMgQ3JlYXRlIGFuIGFyaW1hIG1vZGVsIGZvciBlYWNoIG9mIHRoZW0sIGdpdmVuIHRoYXQgZCxEID0gMS4KI3J1biB0b3RhbCBvZiA4MSBzZXRzIG9mIHBhcmFtZXRlcnMgZm9yIHAscSxQLFEgJWluJSAwOjIKYXJpbWFfcGFyYSA9IGV4cGFuZC5ncmlkKHJlcChsaXN0KDA6MiksIDQpKQphcmltYWxpc3QgPSBsaXN0KCkKZm9yIChpIGluIDE6bnJvdyhhcmltYV9wYXJhKSkgewogIHRyeUNhdGNoKCB7CiAgICBhcmltYWxpc3RbW2ldXSA8LSBydW5hcmltYSh0cmFpbmluZyxhcy5udW1lcmljKGFyaW1hX3BhcmFbaSxdKSwxKQogIH0sCiAgZXJyb3IgPSBmdW5jdGlvbihjb25kKSB7CiAgICByZXR1cm4oTkEpCiAgfQogICkKfQoKI0NoZWNrIG51bGwgbW9kZWxzLiBUaGVzZSBhcmUgbW9kZWxzIHRoYXQgbWlnaHQgYmUgdW5zdGFibGUgYW5kIGNvdWxkbid0IGJlIGJ1aWx0IChubyBzdWl0YWJsZSBwYXJhbWV0ZXJzIGZvdW5kKQpudWxsdmFscyA9ICFzYXBwbHkoYXJpbWFsaXN0LCBpcy5udWxsKQpmaXRsaXN0X25vbnVsbCA9IGFyaW1hbGlzdFtudWxsdmFsc10KcGFyYV9ub251bGwgPSBhcmltYV9wYXJhW251bGx2YWxzLF0KCmFpY2MgPSBsaXN0KCkKZm9yIChpIGluIDE6bGVuZ3RoKGZpdGxpc3Rfbm9udWxsKSkgewogIGFpY2NbW2ldXSA8LSBmaXRsaXN0X25vbnVsbFtbaV1dW1siYWljYyJdXQp9CgojdmlzdWFsaXplIEFJQ0MKYWljYyA9IGFzLm51bWVyaWMoYWljYykKZmNlcnJvcnMgPSBhcy5kYXRhLmZyYW1lKHQoc2FwcGx5KGZpdGxpc3Rfbm9udWxsLCdlcnJvcmNhbGMnLHRlc3QpKSkKCiNjaGVja3BhcmFtZXRlcnMgb2Ygb3B0aW1pemVkIG1vZGVsLCBzZWxlY3RlZCBiYXNlZCBvbiBjb21wYXJpc29uIHdpdGggdGVzdCBzZXQgb3IgQUlDQy4KI1JNU0UsIE1BRSwgQUlDQwpwYXJhX25vbnVsbFt3aGljaC5taW4oZmNlcnJvcnMkUk1TRSksXQpwYXJhX25vbnVsbFt3aGljaC5taW4oZmNlcnJvcnMkTUFFKSxdCnBhcmFfbm9udWxsW3doaWNoLm1pbihhaWNjKSxdCgpwbG90YXJpbWEgPSBsaXN0KGZpdGxpc3Rfbm9udWxsW1t3aGljaC5taW4oZmNlcnJvcnMkUk1TRSldXSxmaXRsaXN0X25vbnVsbFtbd2hpY2gubWluKGZjZXJyb3JzJE1BRSldXSxmaXRsaXN0X25vbnVsbFtbd2hpY2gubWluKGFpY2MpXV0pCgpwbG90YXJpbWFlcnJvciA9IGFzLmRhdGEuZnJhbWUodChzYXBwbHkocGxvdGFyaW1hLCdlcnJvcmNhbGMnLHRlc3QpKSkKZml0cm93cyA9IGMoJ01pbiBSTVNFJywnTWluIE1BRScsJ01pbiBBSUNjJykKcGxvdGFyaW1hZXJyb3IkRml0cyA8LSBhcy5mYWN0b3IoZml0cm93cykKYGBgCgpgYGB7cn0KcGxvdGFyaW1hZXJyb3IgJT4lCiAgbWVsdChpZC52YXJzID0gIkZpdHMiKSAlPiUKICBnZ3Bsb3QoYWVzKHggPSB2YXJpYWJsZSwgeSA9IHZhbHVlKSkgKyAKICBnZW9tX2JhcihhZXMoZmlsbCA9IEZpdHMpLCBzdGF0ID0gJ2lkZW50aXR5JywgcG9zaXRpb24gPSAnZG9kZ2UnKSArIAogIGxhYnModGl0bGUgPSAiRXJyb3JzIG9uIHRlc3Qgc2V0IikgKyBmYWNldF93cmFwKH52YXJpYWJsZSwgc2NhbGUgPSAiZnJlZSIpCmBgYAoKCiMgQ29tcGFyZSB0byB0ZXN0IHNldApgYGB7ciwgbWVzc2FnZT1GQUxTRSwgZmlnLmhlaWdodD00LCBmaWcud2lkdGg9Nn0KYXV0b3Bsb3Qod2luZG93KGFtdHJha3RzLCBzdGFydCA9IGMoMjAxNCwxKSkpICsgbGFicyh5PSJSaWRlcnNoaXAiKSArCiAgYXV0b2xheWVyKGZvcmVjYXN0KHBsb3RhcmltYVtbMV1dLGxlbmd0aCh0ZXN0KSksIHNlcmllcyA9ICdNaW4gUk1TRScsIFBJID0gRkFMU0UpICsKICBhdXRvbGF5ZXIoZm9yZWNhc3QocGxvdGFyaW1hW1syXV0sbGVuZ3RoKHRlc3QpKSwgc2VyaWVzID0gJ01pbiBNQUUnLCBQSSA9IEZBTFNFKSArCiAgYXV0b2xheWVyKGZvcmVjYXN0KHBsb3RhcmltYVtbM11dLGxlbmd0aCh0ZXN0KSksIHNlcmllcyA9ICdNaW4gQUlDYycsIFBJID0gRkFMU0UpICsKICBhbm5vdGF0ZSgicmVjdCIsIHhtaW4gPSAyMDE2LCB4bWF4ID0gMjAxOC41LCB5bWluID0gMTUwMCwgeW1heCA9IDIzMDAsCiAgICAgICAgICAgYWxwaGEgPSAuMSwgZmlsbCA9ICJ5ZWxsb3ciKSArCiAgYW5ub3RhdGUoInRleHQiLCB4ID0gMjAxNi41LCB5ID0gMjI1MCwgbGFiZWwgPSBjKCJUZXN0IFBlcmlvZCIpLCBzaXplID0gMTApCgojU2VsZWN0aW9uIG9mIE1pbiBNQUUgKDExMSwwMTEpIGFuZCBNaW4gUk1TRSAoMjEyLDIxMikgYXMgbW9kZWwuCnNlbGVjdGVkbW9kZWxzID0gbGlzdChmaXRsaXN0X25vbnVsbFtbd2hpY2gubWluKGZjZXJyb3JzJFJNU0UpXV0sZml0bGlzdF9ub251bGxbW3doaWNoLm1pbihmY2Vycm9ycyRNQUUpXV0pCmBgYAoKIyBUcnkgb3V0IGV0cyBtb2RlbApgYGB7cn0KIyBSZWNhbGxpbmcgcHJldmlvdXMgZGVjb21wb3NpdGlvbiBwbG90cywgd2Ugc2hvdWxkIGV4cGVjdCBhZGRpdGl2ZSBzZWFzb25hbGl0eSBhbmQgdHJlbmQgY29tcG9uZW50cy4KI2kuZSBvdXIgZXRzIG1vZGVsIHNob3VsZCB5aWVsZCBldHMoLSxBLEEpCgpmaXRldHMgPSBldHModHJhaW5pbmcpCmZpdGV0cyA9IGV0cyh0cmFpbmluZywgbW9kZWwgPSAiWkFBIikKI21vZGVsIGNob3NlIEFBQSBldHMgbW9kZWwuIAojdHJ5IFpNTSwgWkFNLCBaTUEgbW9kZWxzLCBBSUMgZGlkIG5vdCBpbXByb3ZlLgoKZXRzKHRyYWluaW5nLCBtb2RlbCA9ICJaTU0iKQojIGV0cyh0cmFpbmluZywgbW9kZWwgPSAiWk1BIikKIyBFcnJvciBpbiBldHModHJhaW5pbmcsIG1vZGVsID0gIlpNQSIpIDogTm8gbW9kZWwgYWJsZSB0byBiZSBmaXR0ZWQKCnNlbGVjdGVkbW9kZWxzW1tsZW5ndGgoc2VsZWN0ZWRtb2RlbHMpKzFdXSA8LSBmaXRldHMKCiNDb21wYXJlIGFjY3VyYWN5IGFnYWluc3QgdGVzdCBzZXQuCmFjY3VyYWN5KHByZWRpY3QoZml0ZXRzLCBsZW5ndGgodGVzdCkpLCB0ZXN0KQoKIyBQbG90IGZvcmVjYXN0IGZyb20gRVRTKEEsQSxBKQphdXRvcGxvdCh3aW5kb3coYW10cmFrdHMsIHN0YXJ0ID0gYygyMDEwLDEpKSkgKyBsYWJzKHk9IlJpZGVyc2hpcCIpICsKICBhdXRvbGF5ZXIoZm9yZWNhc3QoZml0ZXRzLGxlbmd0aCh0ZXN0KSksIFBJID0gVFJVRSkgKyAgCiAgbGFicyh0aXRsZSA9ICJGb3JlY2FzdCBmcm9tIEVUUyhBLEEsQSkiKQpgYGAKCiMgVHJ5IHRzQ3YKYGBge3J9CiN1c2UgdHNDViB0byBjaGVjayBvdXIgbW9kZWxzLiBTdGFydCB3aXRoIGV0cy4KbXlmb3JlY2FzdCA9IGZ1bmN0aW9uKHksaCkgewogIGZvcmVjYXN0KGV0cyh5LCBtb2RlbCA9ICJaQUEiKSxoID0gaCkKfQoKUk1TRWNhbGMgPSBmdW5jdGlvbihhKSB7CiAgc3FydChtZWFuKGFeMiwgbmEucm0gPSBUUlVFKSkKfQoKTUFFY2FsYyA9IGZ1bmN0aW9uKGEpIHsKICBtZWFuKGFicyhhKSwgbmEucm0gPSBUUlVFKQp9CgpOQWNhbGMgPSBmdW5jdGlvbihhKSB7CiAgc3VtKGlzLm5hKGEpKQp9CnRzQ1ZldHMgPSB0c0NWKHVwdHJlbmQsIG15Zm9yZWNhc3QsIGggPSAxMikKCiMgY29tcHV0ZSBSTVNFL01BRS9OQSBmb3IgZm9yZWNhc3Qgd2luZG93LiBXZSBhbHNvIHJlbW92ZSB0aGUgZmlyc3QgMTQgZmlndXJlcyBhcyBhcmltYSBjYW5ub3QgYnVpbGQgYSBtb2RlbCB3aXRob3V0IDEgeWVhciBvZiBzZWFzb25hbGl0eS4KdHNDVmV0cyA9IHdpbmRvdyh0c0NWZXRzLCBzdGFydCA9IGMoMjAxMSwzKSkKClJNU0VldHMgPSBhcHBseSh0c0NWZXRzLCAyLCBSTVNFY2FsYykKTUFFZXRzID0gYXBwbHkodHNDVmV0cywgMiwgTUFFY2FsYykKTkFldHMgPSBhcHBseSh0c0NWZXRzLCAyLCBOQWNhbGMpCgojdHNDViBvbiBhcmltYSgyMTIsMjEyKQpteWZvcmVjYXN0ID0gZnVuY3Rpb24oeSxoKXsKICBmb3JlY2FzdChhcmltYSh5LCBvcmRlciA9IGMoMiwxLDIpLCBzZWFzb25hbCA9IGMoMiwxLDIpKSxoID0gaCkKfQoKdHNDVmFyaW1hMjEyMjEyID0gdHNDVih1cHRyZW5kLCBteWZvcmVjYXN0LCBoID0gMTIpCnRzQ1ZhcmltYTIxMjIxMiA9IHdpbmRvdyh0c0NWYXJpbWEyMTIyMTIsIHN0YXJ0ID0gYygyMDExLDMpKQoKUk1TRWFyaW1hMiA9IGFwcGx5KHRzQ1ZhcmltYTIxMjIxMiwgMiwgUk1TRWNhbGMpCk1BRWFyaW1hMiA9IGFwcGx5KHRzQ1ZhcmltYTIxMjIxMiwgMiwgTUFFY2FsYykKTkFhcmltYTIgPSBhcHBseSh0c0NWYXJpbWEyMTIyMTIsIDIsIE5BY2FsYykKCm15Zm9yZWNhc3QgPSBmdW5jdGlvbih5LGgpewogIGZvcmVjYXN0KGFyaW1hKHksIG9yZGVyID0gYygxLDEsMSksIHNlYXNvbmFsID0gYygwLDEsMSkpLGggPSBoKQp9Cgp0c0NWYXJpbWExMTEwMTEgPSB0c0NWKHVwdHJlbmQsIG15Zm9yZWNhc3QsIGggPSAxMikKdHNDVmFyaW1hMTExMDExID0gd2luZG93KHRzQ1ZhcmltYTExMTAxMSwgc3RhcnQgPSBjKDIwMTEsMykpCgpSTVNFYXJpbWExID0gYXBwbHkodHNDVmFyaW1hMTExMDExLCAyLCBSTVNFY2FsYykKTUFFYXJpbWExID0gYXBwbHkodHNDVmFyaW1hMTExMDExLCAyLCBNQUVjYWxjKQpOQWFyaW1hMSA9IGFwcGx5KHRzQ1ZhcmltYTExMTAxMSwgMiwgTkFjYWxjKQoKUk1TRSA9IGFzLmRhdGEuZnJhbWUoY2JpbmQoUk1TRWV0cyxSTVNFYXJpbWEyLFJNU0VhcmltYTEpKQpjb2xuYW1lcyhSTVNFKSA9IGMoImV0c0FBQSIsImFyaW1hMjEyMjEyIiwiYXJpbWExMTEwMTEiKQpSTVNFID0gUk1TRSAlPiUKICByb3duYW1lc190b19jb2x1bW4oImgiKSAlPiUKICBtdXRhdGUoZXJyb3IgPSAiUk1TRSIpCgpNQUUgPSBhcy5kYXRhLmZyYW1lKGNiaW5kKE1BRWV0cyxNQUVhcmltYTIsTUFFYXJpbWExKSkKY29sbmFtZXMoTUFFKSA9IGMoImV0c0FBQSIsImFyaW1hMjEyMjEyIiwiYXJpbWExMTEwMTEiKQpNQUUgPSBNQUUgJT4lCiAgcm93bmFtZXNfdG9fY29sdW1uKCJoIikgJT4lCiAgbXV0YXRlKGVycm9yID0gIk1BRSIpCgpOQXMgPSBhcy5kYXRhLmZyYW1lKGNiaW5kKE5BZXRzLE5BYXJpbWEyLE5BYXJpbWExKSkKY29sbmFtZXMoTkFzKSA9IGMoImV0c0FBQSIsImFyaW1hMjEyMjEyIiwiYXJpbWExMTEwMTEiKQpOQXMgPSBOQXMgJT4lCiAgcm93bmFtZXNfdG9fY29sdW1uKCJoIikgJT4lCiAgbXV0YXRlKGVycm9yID0gIk5BcyIpCgplcnJvcnMgPSByYmluZChSTVNFLE1BRSxOQXMpICU+JQogIG1lbHQoaWQudmFycyA9IGMoImgiLCJlcnJvciIpLCB2YXJpYWJsZS5uYW1lID0gIm1vZGVsIikKCmVycm9ycyRoICU+JQogIHN0cl9leHRyYWN0KCJcXGR7MSwyfSIpICU+JQogIGFzLmludGVnZXIoKSAtPiBlcnJvcnMkaAoKZXJyb3JzICU+JQogIGZpbHRlcihlcnJvciA9PSAiTkFzIikgJT4lIGZpbHRlcihoID09IDEpICU+JQogIGdncGxvdChhZXMoeCA9IG1vZGVsKSkgKwogIGdlb21fY29sKGFlcyh5PXZhbHVlLCBmaWxsPW1vZGVsKSkgKyBmYWNldF93cmFwKH5lcnJvcikgKwogIGxhYnModGl0bGUgPSAiVFMgQ3Jvc3MgVmFsaWRhdGlvbiBSZXN1bHRzIikgKyB4bGFiKCJNb2RlbCIpICsgeWxhYigiTnVtYmVyIG9mIFVuc3RhYmxlIE1vZGVscyIpICsKICBzY2FsZV9maWxsX21hbnVhbCh2YWx1ZXMgPSBjKCIjMjJiOGQ2IiwgIiM0OTIyZDYiLCIjMjI4Yjc1IikpCgplcnJvcnMgJT4lCiAgZmlsdGVyKGVycm9yICE9ICJOQXMiKSAlPiUgZmlsdGVyKG1vZGVsICE9ICJhcmltYTIxMjIxMiIpICU+JQogIGdncGxvdChhZXMoeCA9IGgsIHk9dmFsdWUsIGNvbG9yPW1vZGVsKSkgKwogIGdlb21fc21vb3RoKHNlID0gRkFMU0UsIHNpemUgPSAxLjUpICsKICBnZW9tX3BvaW50KHNpemUgPSAyKSArIAogIGZhY2V0X3dyYXAofmVycm9yLCBucm93ID0gMykgKwogIGxhYnModGl0bGUgPSAiVFMgQ3Jvc3MgVmFsaWRhdGlvbiBSZXN1bHRzIikgKyAKICBzY2FsZV94X2NvbnRpbnVvdXMoYnJlYWtzID0gc2VxKDEsIDEyLCBieSA9IDEpKSArCiAgc2NhbGVfY29sb3JfbWFudWFsKHZhbHVlcyA9IGMoIiMyMmI4ZDYiLCAiIzIyOGI3NSIpKQpgYGAKCiMjIFJldHJhaW4gY29tcGxldGUgbW9kZWwgdG8gZm9yZWNhc3QgNiBtb250aHMgZm9yd2FyZApgYGB7ciwgbWVzc2FnZT1GQUxTRSwgZmlnLmhlaWdodD00LCBmaWcud2lkdGg9Nn0KZml0YXJpbWFfY29tcGxldGUgPSBhcmltYSh1cHRyZW5kLCBvcmRlciA9IGMoMSwxLDEpLCBzZWFzb25hbCA9IGMoMCwxLDEpKQpmaXRldHNfY29tcGxldGUgPSBldHModXB0cmVuZCwgbW9kZWwgPSAiWkFBIikKCgphdXRvcGxvdCh3aW5kb3coYW10cmFrdHMsIHN0YXJ0ID0gYygyMDE2LDEpKSkgKyBsYWJzKHk9IlJpZGVyc2hpcCIpICsKICBhdXRvbGF5ZXIoZm9yZWNhc3QoZml0YXJpbWFfY29tcGxldGUsMTIpLCBzZXJpZXMgPSAnQXJpbWEgMTExMDExJywgUEkgPSBGQUxTRSwgYWxwaGEgPSAwLjUpICsKICBhdXRvbGF5ZXIoZm9yZWNhc3QoZml0ZXRzX2NvbXBsZXRlLDEyKSwgc2VyaWVzID0gJ0VUUyAiQUFBIicsIFBJID0gRkFMU0UsIGFscGhhID0gMC41KSArCiAgc2NhbGVfY29sb3JfbWFudWFsKHZhbHVlcyA9IGMoInJlZCIsImdyZWVuIikpKwogIGFubm90YXRlKCJyZWN0IiwgeG1pbiA9IDIwMTguMjUsIHhtYXggPSAyMDE4Ljc1LCB5bWluID0gMTcwMCwgeW1heCA9IDI0MDAsCiAgICAgICAgICAgYWxwaGEgPSAuMiwgZmlsbCA9ICJibHVlIikgKwogIGFubm90YXRlKCJyZWN0IiwgeG1pbiA9IDIwMTguNzUsIHhtYXggPSAyMDE5LjI1LCB5bWluID0gMTcwMCwgeW1heCA9IDI0MDAsCiAgICAgICAgICAgYWxwaGEgPSAuMSwgZmlsbCA9ICJ5ZWxsb3ciKSArCiAgYW5ub3RhdGUoInRleHQiLCB4ID0gYygyMDE4LjUsMjAxOSksIHkgPSBjKDE4MDAsMTgwMCksIGxhYmVsID0gYygiQXByLVNlcCAnMTgiLCJPY3QtTWFyICcxOSIpLCBzaXplID0gNikgKyAKICBsYWJzKHRpdGxlID0gIkFtdHJhayByaWRlcnNoaXAgZm9yZWNhc3QiKQoKcDEgPSBhdXRvcGxvdCh3aW5kb3coYW10cmFrdHMsIHN0YXJ0ID0gYygyMDE0LDEpKSkgKyBsYWJzKHk9IlJpZGVyc2hpcCIpICsKICBhdXRvbGF5ZXIoZm9yZWNhc3QoZml0YXJpbWFfY29tcGxldGUsMTIpLCBzZXJpZXMgPSAnQXJpbWEgMTExMDExJywgUEkgPSBUUlVFLCBjb2xvdXIgPSAicmVkIikgKyAKICBsYWJzKHRpdGxlID0gImZvcmVjYXN0IHdpdGggQXJpbWExMTEwMTEiKQoKcDIgPSBhdXRvcGxvdCh3aW5kb3coYW10cmFrdHMsIHN0YXJ0ID0gYygyMDE0LDEpKSkgKyBsYWJzKHk9IlJpZGVyc2hpcCIpICsKICBhdXRvbGF5ZXIoZm9yZWNhc3QoZml0YXJpbWFfY29tcGxldGUsMTIpLCBzZXJpZXMgPSAnZXRzX0FBQScsIFBJID0gVFJVRSwgY29sb3VyID0gImdyZWVuIikgKyAKICBsYWJzKHRpdGxlID0gImZvcmVjYXN0IHdpdGggZXRzX0FBQSIpCgpmb3JlY2FzdGFyaW1hID0gZm9yZWNhc3QoZml0YXJpbWFfY29tcGxldGUsIDEyKQpmb3JlY2FzdGV0cyA9IGZvcmVjYXN0KGZpdGV0c19jb21wbGV0ZSwxMikKCmdnYXJyYW5nZShwMSxwMixucm93ID0gMiwgbmNvbCA9IDEpCgpgYGAK